import org.junit.Test;
import test.ListNode;

/**
 * 合并两个有序链表
 */
public class RemoveDuplicates {

    @Test
    public void MergeOrderList() {

        ListNode n5 = new ListNode(4);
        ListNode n4 = new ListNode(4, n5);
        ListNode n3 = new ListNode(2, n4);
        ListNode n2 = new ListNode(2, n3);
        ListNode l1 = new ListNode(1, n2);

        long startTime1 = System.currentTimeMillis();
        ListNode del1 = del(l1);
        long endTime1 = System.currentTimeMillis();
        System.out.println("del1=" + del1 + ",使用时间:" + (endTime1 - startTime1));

        long startTime2 = System.currentTimeMillis();
        ListNode del2 = del2(l1);
        long endTime2 = System.currentTimeMillis();
        System.out.println("del2=" + del2 + ",使用时间:" + (endTime2 - startTime2));

    }

    /**
     * 使用遍历删除重复节点
     * @param head 源节点
     * @return 删除重复元素后节点
     */
    public static ListNode del(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode currentNode = head;
        while (currentNode.getNext() != null) {
            if (currentNode.getVal() == currentNode.getNext().getVal()) {
                //当前值等于下一节点值，则将当前值的下一节点置为下下一节点
                currentNode.setNext(currentNode.getNext().getNext());
            } else {
                //当前值不等于下一节点，则将当前值设为下一节点
                currentNode = currentNode.getNext();
            }
        }
        return head;
    }

    /**
     * 使用递归压栈处理
     * @param head 原始节点
     * @return 删除重复元素后节点
     */
    public static ListNode del2(ListNode head) {
        if (head == null || head.getNext() == null) {
            return head;
        }
        head.setNext(del2(head.getNext()));
        //当前值等于下一节点值，则取下一节点返回，否则返回当前节点值
        return head.getVal() == head.getNext().getVal() ? head.getNext() : head;
    }
}
